/*
 * graph.c
 *
 *  Created on: Dec 16, 2011
 *      Author: sanglei
 * description: 关于图的一些操作
 *
 * 附：
 * 该图仅适合于图中节点ID是从1开始的整数，如 1、2、3、4、5、6
 */
#include <assert.h>
#include <stdlib.h>
#include "headers/graph.h"

#define EDGE_MAX_VEX 200 //节点v的所有链接节点个数

int add_edge(ALGraph *const graph,int s,int e){
	assert(graph!=NULL);
	assert(s!=0 && s!=-1 && e!=0 && e!=-1);

	Vnode *node,*head = graph->fArray+s;
	assert(head!=NULL);
	if(head->vex == -1){
		head->vex = e;
		head->next = NULL;
	}else{
		node = (Vnode *)malloc(sizeof(Vnode));
		node->vex = e;

		//插入到链表中
		node->next = head->next;
		head->next = node;
	}

	return 1;
}

int init_graph(ALGraph * const graph,const char *const path){
	assert(graph!=NULL);
	assert(path!=NULL);
	FILE * fp;
	int vSize,eSize;

	if((fp=fopen(path,"r"))==NULL){
		return 0;
	}

	fscanf(fp,"%d%d",&vSize,&eSize);//读取的过程中，遇到"\n"则处理掉
	graph->fArray = (Vnode *)malloc(sizeof(Vnode)*(vSize+1));
	graph->vexSize = vSize;

	//将数组中的所有Vnode初始化,如果不这么做，则他们都是"野值"
	int i;
	for(i=1;i<=vSize;i++){
		graph->fArray[i].vex = -1;
		graph->fArray[i].next = NULL;
	}

	int start,end;//边的起始节点
	while(fscanf(fp,"%d-%d",&start,&end) == 2){//fscanf的返回值是转换成功的个数，如果到达结尾则返回EOF
		add_edge(graph,start,end);
		add_edge(graph,end,start);//无向图
	}

	fclose(fp);
	return 1;
}

int * get_neighbors(ALGraph * const graph,int vid){
	assert(graph!=NULL);

	int vsize=0;

	int *p,*res = (int*)malloc(sizeof(int)*EDGE_MAX_VEX);//
	assert(res!=NULL);
	p = res;
	Vnode *pnode = &(graph->fArray)[vid];
	while(pnode!=NULL && pnode->vex!=-1){
		*p++ = pnode->vex;
		pnode = pnode->next;
		vsize++;
	}

	if(vsize == 0){
		return NULL;
	}else{
		*p = -1;//终止符
		return res;
	}
}

int drop_graph(ALGraph * const graph){
	assert(graph!=NULL);
	Vnode * p = graph->fArray,*q;
	int i;
	for(i=1;i<= graph->vexSize;i++){
		while((q=&p[i])!=NULL){
			free(q);
			p = p->next;
		}
	}
	free(p);
	return 1;
}

void print_graph(ALGraph * const graph){
	assert(graph!=NULL);

	int i;
	for(i=1;i<=graph->vexSize;i++){
		Vnode *tmp = &(graph->fArray[i]);
		printf("%d:",i);
		while(tmp!=NULL && tmp->vex != -1){
			printf("%d ",tmp->vex);
			tmp = tmp->next;
		}
		printf("\n");
	}
}

void main_graph(){
	ALGraph graph;
	init_graph(&graph,"data/graph.txt");
	print_graph(&graph);
	drop_graph(&graph);
}
